A basic function required of a conventional circuit-switched communication network is one of routing a service request through the network and then establishing a connection between an originating point and a destination point according to the route selected. In the terminology of telephony, this activity is often described as a calling party placing a call to a called party. The call is established on a path through the network designated a route. In turn, a route may be comprised of one or more intermediate points or nodes interconnected to other nodes by one or more links or trunk groups comprising servers or trunks. Finally, each server or trunk is basically a single transmission path such as a cable pair. Thus, a circuit-switched connection is characterized by the selection of a route through the network that is fixed for the duration of a call, i.e., the particular servers are dedicated to the call for its duration. Examples of such networks are the conventional analog intra-LATA (Local Access and Transport Area) telephone network and the analog inter-LATA (that is, long distance) telephone network.
Historically, traffic routing techniques were devised for so-called time-invariant, hierarchical, circuit-switched networks. In a hierarchical plan, nodes are assigned to a geographical area designated a "region" and each node is given a "rank." Under the plan, any node homes on another node of higher rank within the same region, but not on a node of lower rank. Such a plan effectively dictates the link connections between specific node-pairs; it followed, quite naturally, that traffic routing techniques were developed within the constraint of the hierarchical arrangement of nodes and very little flexibility was offered for devising other routing plans that may have emerged if node interconnection constraints had not been imposed. In fact, even in the hierarchical plan, it occasionally happens that the traffic, e.g., the call, is blocked either involuntarily or voluntarily. An involuntary blocking occurs when no route through the network can be found which has at least one free trunk in all the trunk groups. A voluntary blocking occurs when, even though an available route can be found, the call is blocked to protect future call attempts. A voluntary blocking may be indicated when the only available routes all go over two or more trunk group, with a sizable risk that carrying one more call now will lead to multiple call blockings.
With the advent of digital switches and data transmission techniques over cable and fiber media, packet-switched networks have been recently introduced. These networks are characterized by a time-sharing of servers comprising the links interconnecting network nodes. Initially, each message, e.g., a portion or sample of an analog telephone conversation, is digitized into an appropriate digital format. Then each digital message to be transmitted from a source node to a destination node is "packetized", that is, the digitized message is augmented with header information such as the source and destination addresses as well as trailer information for discerning the end of the packet. Each packet is transmitted on a given link in a time interval or slot selected from many slots generally available for transmission between node-pairs. Because of the detailed information embedded in the packet, the packet is self-routing in the sense that each node in the network can parse the contents of each packet in order to determine the processing required of a node-either forwarding the packet if the node is not the destination node, or detecting the packet message if the node is the desired destination node. Due to the discretization in packet transmission, timing information is important in a packet system so as to piece together segments of a conversation and restore intelligibility. However, this timing concern is more at the "local" or physical level and can be appropriately arranged once a network configuration and a "global" or logical routing strategy have been devised.
As alluded to above, newly installed packet systems no longer have imposed constraints like those of the hierarchical plan. Once a node pattern has been established or adopted, the interconnection of network nodes is unencombered in the sense that the conventional hierarchical rules do not apply. However, even in packet systems, after a configuration has been devised, techniques for efficiently routing packet traffic through the system still must be addressed.